package leetcode.code0957;

import java.util.TreeMap;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * dp <br>
 * 最后一个用例 暴力需要30倍时间 <br>
 * 从哪里出发能抵达会有很多无用的尝试 <br>
 * 从哪里来能到这里, 效果更好 <br>
 *
 * @author CaoYu
 * @date 2021年9月30日
 * @description
 */
public class Solution957 implements IDebug {

	public int oddEvenJumps(int[] arr) {
		int len = arr.length;
		TreeMap<Integer, Integer> map = new TreeMap<>();// 距离当前数值最近的数值 & 下标 (重复中最近)
		map.put(arr[len - 1], len - 1);// 最后一个值入备选集合
		Boolean[][] dp = new Boolean[len][2];// dp[i][0]从当前位置i(站在i上),奇数步出发是否可以抵达最后一个格子 , 1是偶数步
		dp[len - 1][0] = true;// 最后一个格子,抵达则达成条件(站在len-1上)
		dp[len - 1][1] = true;// 最后一个格子,抵达则达成条件(站在len-1上)
		int ans = 1;
		for (int index = len - 2; index >= 0; index--) {// 倒着走,从后往前走
			Integer ceil = map.ceilingKey(arr[index]);// 找A[i] <= A[j],当前奇数步出发,是否有后续能接纳的位置
			Integer floor = map.floorKey(arr[index]);// A[i] >= A[j],当前偶数步出发,是否有后续能接纳的位置
			dp[index][0] = ceil == null ? false : dp[map.get(ceil)][1];// ==null,后续没有格子,当前奇数步出发,不能抵达.否则取决于后续偶数步是否能抵达
			dp[index][1] = floor == null ? false : dp[map.get(floor)][0];// 同上,给前面奇数步出发垫步用的,对于当前点没用.
			if (dp[index][0]) {// 起脚就是奇数; 判断当前点, 作为首发出发是否能抵达
				ans++;// 能, 就多一种方案
			}
			map.put(arr[index], index);// 当前点加入备选列表,给index--用.只能在当前阶段处理后加入,否则被当成后面的点,就错了.
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[10,13,12,14,15]";
		int e = 2;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,3,1,1,4]";
		int e = 3;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[5,1,3,4,2]";
		int e = 3;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String str = "[1,2,3,2,1,4,4,5]";
		int e = 6;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	// [31,28,8,41,20,28,41,26,46,30,
	// 41,34,2,29,24,39,28,11,22,21,
	// 33,15,14,35,49,23,
	// 15,46,19,28,13,19,38]//index 26 -> 28 -> 31 -> 32
	public void debug5() {
		String str = "[31,28,8,41,20,28,41,26,46,30,41,34,2,29,24,39,28,11,22,21,33,15,14,35,49,23,15,46,19,28,13,19,38]";
		int e = 21;
		int r = this.oddEvenJumps(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public static void main(String[] args) {
		Solution957 so = new Solution957();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
